package TG_54;

import java.util.LinkedList;
import java.util.List;

public class Solution {
	public List<Integer> spiralOrder(int[][] matrix) {
		List<Integer> res = new LinkedList<Integer>();
		if (matrix.length == 0) {
			return res;
		}
		int r1 = 0, r2 = matrix.length - 1;
		int c1 = 0, c2 = matrix[0].length - 1;
		while (r1 <= r2 && c1 <= c2) {
			for (int c = c1; c <= c2; c++) {
				res.add(matrix[r1][c]);
			}
			for (int r = r1 + 1; r <= r2; r++) {
				res.add(matrix[r][c2]);
			}
			if (r1 < r2 && c1 < c2) {
				for (int c = c2 - 1; c > c1; c--) {
					res.add(matrix[r2][c]);
				}
				for (int r = r2; r > r1; r--) {
					res.add(matrix[r][c1]);
				}

			}
			r1++;
			c2--;
			c1++;
			r2--;
		}

		return res;
	}
	
	public int[] spiralOrder_m2(int[][] matrix) {
		if (matrix.length == 0) {
			return new int[0];
		}
		int l = 0, r = matrix[0].length-1, t = 0, b = matrix.length-1,count=0;
		int[] res = new int[(r+1)*(b+1)];
		while (true) {
			for (int i = l; i <= r; i++) {
				res[count++]=matrix[t][i];
			}
			if (++t>b) {
				break;
			}
			for (int i = t; i <= b; i++) {
				res[count++]=matrix[i][r];
			}
			if (l>--r) {
				break;
			}
			for (int i = r; i >= l ; i--) {
				res[count++]=matrix[b][i];
			}
			if (t>--b) {
				break;
			}
			
			for (int i = b; i >= t; i--) {
				res[count++]=matrix[i][l];
			}
			if (++l>r) {
				break;
			}
		}
		return res;
	}
	
	
	
}
